备用返回通道

转到题目

前备知识Trie

异或和之差

题目描述

给定一个含有 n 个元素的数组 A[i]，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。

输入格式

• 输入的第一行包含一个整数 n。
• 第二行包含 n 个整数 A[i]，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

6
1 2 4 9 2 7

样例输出

14

样例说明

两个子段可以分别选 [1] 和 [4, 9, 2]，差值为 15 - 1 = 14。

评测用例规模与约定

• 对于 40 的评测用例，n ≤ 5000；
• 对于所有评测用例，2 ≤ n ≤ 2 × 10^5，0 ≤ A[i] ≤ 2^20。

运行限制

| 语言 | 最大运行时间 | 最大运行内存 | | ———— | ———— | ———— | | C++ | 1s | 256M | | C | 1s | 256M | | Java | 2s | 256M | | Python3 | 10s | 256M | | PyPy3 | 10s | 256M | | Go | 10s | 256M | | JavaScript | 10s | 256M | —

题目思路

• 子区间异或和之差，暴力枚举将会达到$O(n^4) $
• 为了优化复杂度，我们线性拆分
  • 枚举每个位置的左侧子区间 与 右侧子区间 的异或和之差最大值的情况

• 我们为什么要这样拆呢?

  • 子问题可以转化为 前/后缀 子区间异或和极值 问题

  • 而转化后，就可以用**前缀树

    字典树 Tire**来求解